1. Field of the Invention
This invention relates to resource scheduling and, more particularly, to dynamic hierarchial resource scheduling for continuous media based on initial conservative estimates and then slack filling.
2. Description of the Related Art
As loads increase on computers and workstations, smooth playout of continuous media streams have had greater difficulty in being maintained because of the computer's loss of Central Processor Unit (CPU) cycles and network and disk bandwidth, leading to delayed transfers. Demand has risen for continuous media service on networks of conventional workstations and personal computers running common operating systems that can handle more strenuous loads. But the normal mechanisms in this environment provide resource allocation with no allowance for time-sensitive behavior.
In order for media service to maintain a continuous stream of data, resources need to be managed to avoid shortages that would cause interruptions. In general, the most of the prior art has been geared toward hard, real-time scheduling. This approach requires an environment where every latency and resource requirement is known. See D. Niehaus, et al. The Spring Scheduling Co-Processor: Design, Use and Performance; In Proceedings Real-Time Systems Symposium Raleigh-Durham N.C., pgs. 106-111, December 1993; and K. Schwan et al., Dynamic Scheduling of Hard Real-Time Tasks and Real-Time Threads, IEEE Transactions on Software Engineering, 18(8): 736-748, August 1992. Hard real-time scheduling is computationally expensive, and is not normally possible in general timesharing environments characterized by unpredictable resources and delays.
A second common approach has been with conservative resource usage estimates. Admission control limits the service load to that known to be safe in the worst case, or known to be safe with high probability. See, for example, D. P. Anderson, Metascheduling for continuous media. ACM Transactions on Computer Systems, 11(3):226-252, August 1993 and D. P. Anderson et al.; a file system for continuous media; ACM Transactions on Computer Systems, 10(4):311-337, 1992. However, conservative estimates lead to low utilization in a general operating system setting.
Admission control and resource scheduling can also be performed by a model of the resources available and the resource consumption demanded by a new request. As an example, see P. Loucher et al.; The Design Of A Storage Server For Continuous Media, The Computer Journal, 36(1):2-42, 1993. One problem here is that a resource model of the system cannot be both highly accurate and inexpensively computed, particularly for general timesharing environments. Another problem is that the precise resource consumption implied by a new request for service is generally unknown.
The above approaches generally share the "admission control assumption", namely that a request for service should either be refused immediately, or should be guaranteed good service. To support the admission control assumption, the systems must place fairly strong requirements on the determinism and predictability of the system and workload.